/**
 * 
 */
package algorithm.passed2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import utils.PrintUtils;

/**
 * @author xyyi
 *
 */
public class WordLadderII {

    /**
    Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

    Only one letter can be changed at a time
    Each intermediate word must exist in the dictionary
    For example,

    Given:
    start = "hit"
    end = "cog"
    dict = ["hot","dot","dog","lot","log"]

    Return

    [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
    ]
    Note:

    All words have the same length.
    All words contain only lowercase alphabetic characters.
    
    http://www.cnblogs.com/shawnhue/archive/2013/06/05/leetcode_126.html
     */
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {

        Set<String> visited = new HashSet<String>();
        Queue<String> queue = new LinkedList<String>();
        Map<String, List<String>> backtrace = new HashMap<String, List<String>>();
        
        queue.offer(start);

        while (!queue.isEmpty()) {
        	Iterator<String> itr = queue.iterator();
        	while (itr.hasNext())
        		visited.add(itr.next());

        	for (int length = queue.size(); length >= 1; length--) {
        		String word = queue.poll();
        		for (int i = 0; i < start.length(); i++) {
        			StringBuilder sb = new StringBuilder();
        			for (char ch = 'a'; ch <= 'z'; ch++) {
        				sb.setCharAt(i, ch);
        				String newWord = sb.toString();
        				if (!visited.contains(newWord)
        						&& dict.contains(newWord)) {
        					queue.offer(newWord);
        					updateBacktrace(backtrace, newWord, word);
        				}
        			}
        		}
        	}
            if (backtrace.containsKey(end)) {
                break;
            }
        }

        List<List<String>> paths = new ArrayList<>();
        if (backtrace.containsKey(end))
            buildPath(end, backtrace, paths, new LinkedList<String>());

        return paths;
    }

    public List<List<String>> findLaddersTwoSets(String start, String end, Set<String> dict) {

        Set<String> visited = new HashSet<>();
        Set<String> unvisited = new HashSet<>(dict);
        Queue<String> queue = new LinkedList<String>();
        Map<String, List<String>> backtrace = new HashMap<String, List<String>>();
        
        queue.offer(start);
        unvisited.add(end);
        unvisited.remove(start);

        while (!queue.isEmpty()) {
            for (int length = queue.size(); length >= 1; length--) {
                String word = queue.poll();
                for (int i = 0; i < start.length(); i++) {
                    StringBuilder sb = new StringBuilder(word);
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                    	sb.setCharAt(i, ch);
                    	String newWord = sb.toString();
                    	if (unvisited.contains(newWord)) {
                    		if (visited.add(newWord)) {
                    			queue.offer(newWord);
                    		}
                    		updateBacktrace(backtrace, newWord, word);
                    	}
                    }
                }
            }
            if (backtrace.containsKey(end)) {
                break;
            }
            else {
            	unvisited.removeAll(visited);
            	visited.clear();
            }
        }

        List<List<String>> paths = new ArrayList<>();
        if (backtrace.containsKey(end))
            buildPath(end, backtrace, paths, new LinkedList<String>());

        return paths;
    }  
    
    // DFS
    private void buildPath(String word,
            Map<String, List<String>> backtrace,
            List<List<String>> paths, LinkedList<String> buffer) {

        buffer.addFirst(word);
        if (backtrace.get(word) == null) {
            paths.add(new ArrayList<String>(buffer));
        } else {
            List<String> list = backtrace.get(word);
            for (String str : list) {
                buildPath(str, backtrace, paths, buffer);
            }
        }
        buffer.removeFirst();
    }

    private void updateBacktrace(Map<String, List<String>> backtrace,
            String word, String preWord) {
        if (backtrace.containsKey(word)) {
        	backtrace.get(word).add(preWord);
        } else {
            LinkedList<String> list = new LinkedList<String>();
            list.add(preWord);
            backtrace.put(word, list);
        }
    }

    /**
     * Word Ladder CareerCup 150
     */
    public List<String> findOneLadderLC(String start, String end, Set<String> dict) {
    	List<String> result = new LinkedList<>();
    	if (!dict.contains(start) || !dict.contains(end))
    		return result;

    	Queue<String> wordsQueue = new LinkedList<>();
    	Set<String> visitedWords = new HashSet<>();
    	Map<String, String> backtrace = new HashMap<>();
    	
    	wordsQueue.offer(start);
    	visitedWords.add(start);
    	
    	while (!wordsQueue.isEmpty()) {
    		for (int queueSize = wordsQueue.size(); queueSize >= 0; queueSize--) {
    			final String word = wordsQueue.poll();
    			for (int i = 0; i < word.length(); i++) {
    				StringBuilder sb = new StringBuilder(word);
    				for (char ch = 'a'; ch <= 'z'; ch++) {
    					sb.setCharAt(i, ch);
    					final String newWord = sb.toString();
    					if (newWord.equals(end)) {
    						backtrace.put(newWord, word);
    						result = buildPath(backtrace, newWord);
    						return result;
    					}
    					if (!visitedWords.contains(newWord) && dict.contains(newWord)) {
    						wordsQueue.offer(newWord);
    						visitedWords.add(newWord);
    						backtrace.put(newWord, word);
    					}
    				}
    			}
    		}
    	}
    	
    	return result;
    }
    
    private List<String> buildPath(Map<String, String> backtrace, String start) {
    	LinkedList<String> path = new LinkedList<>();
    	String word = start;
    	
    	while (word != null) {
    		path.addFirst(word);
    		word = backtrace.get(word);
    	}
    	
    	return path;
    }
    
    public List<String> findOneLadderOld(String start, String end,
            Set<String> dict) {
        LinkedList<String> result = new LinkedList<String>();
        Queue<String> queue = new LinkedList<String>();
        Map<String, String> backtrack = new HashMap<String, String>();
        Set<String> visited = new HashSet<String>();
        start = start.toLowerCase();
        end = end.toLowerCase();
        queue.offer(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            String word = queue.poll();
            char[] chars = word.toCharArray();
            for (int i = 0; i < word.length(); i++) {
                char curr = chars[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c != curr) {
                        chars[i] = c;
                        String newWord = new String(chars);
                        if (newWord.equals(end)) {
                            result.addFirst(newWord);
                            while (word != null) {
                                result.addFirst(word);
                                word = backtrack.get(word);
                            }
                            return result;
                        }

                        if (!visited.contains(newWord)
                                && dict.contains(newWord)) {
                            queue.offer(newWord);
                            visited.add(newWord);
                            backtrack.put(newWord, word);
                        }
                    }
                }
            }
        }

        return result;
    }

    public WordLadderII() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        WordLadderII wlii = new WordLadderII();
        String start = "red";
        String end = "tax";
        HashSet<String> dict = new HashSet<String>();
        dict.add("ted");
        dict.add("tex");
        dict.add("red");
        dict.add("tax");
        dict.add("tad");
        dict.add("den");
        dict.add("rex");
        dict.add("pee");
        List<String> path = wlii.findOneLadderLC(start, end, dict);
        PrintUtils.printList(path);
        //"red", "tax", ["ted","tex","red","tax","tad","den","rex","pee"]
    }

}
